package hero.mps.sort;

import java.util.Arrays;

public class CountSort {

    /**
     * 计数排序算法
     *
     * @param array 待排序的整数数组
     * @return 排序后的整数数组
     */
    public static int[] countSort(int array[]) {
        // 找出数组中的最大值
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        // 创建一个计数数组，长度为最大值加1
        int[] countArray = new int[max + 1];
        for (int i = 0; i < array.length; i++) {
            // 统计每个数字出现的次数
            countArray[array[i]]++;
        }

        // 创建一个排序后的数组
        int index = 0;
        int[] sortedArray = new int[array.length];
        for (int i = 0; i < countArray.length; i++) {
            // 依次将每个数字按照出现次数放入排序后的数组
            for (int j = 0; j < countArray[i]; j++) {
                sortedArray[index++] = i;
            }
        }

        // 返回排序后的数组
        return sortedArray;
    }

    /**
     * 对数组进行计数排序优化
     *
     * @param array 待排序的数组
     * @return 排序后的数组
     */
    public static int[] countSortOptimize(int array[]) {
        // 找到数组中的最大值和最小值
        int max = array[0];
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }

        // 根据最大值和最小值创建计数数组
        int[] countArray = new int[max -min + 1];
        for (int i = 0; i < array.length; i++) {
            // 统计每个数字出现的次数
            countArray[array[i] - min]++;
        }

        // 计算前缀和
        int sum = 0;
        for (int i = 0; i < countArray.length; i++) {
            sum += countArray[i];
            // 更新计数数组为前缀和
            countArray[i] = sum;
        }

        // 创建排序后的数组
        int[] sortedArray = new int[array.length];
        for (int i = array.length - 1; i >= 0 ; i--) {
            // 根据计数数组将元素放入正确的位置
            sortedArray[countArray[array[i] - min] -1] = array[i];
            // 更新计数数组
            countArray[array[i] - min]--;
        }

        return sortedArray;
    }



    public static void main(String[] args) {
        int[] array = {1, 5, 2, 3, 4, 1, 1,3, 2};
        int[] sortedArray = countSortOptimize(array);
        System.out.println(Arrays.toString(sortedArray));
    }
}
